package cn.sciento.core.algorithm.structure;

import org.springframework.util.CollectionUtils;

import java.util.*;

public class LinkedQueue<T> implements Collection<T> {
    private LinkedList<T> list;

    private Comparator<T> comparator;

    public LinkedQueue(Comparator<T> comparator) {
        this.list = new LinkedList<>();
        this.comparator = comparator;
    }

    public LinkedQueue(List<T> list, Comparator<T> comparator) {
        list.sort(comparator);
        this.list = new LinkedList<>(list);
    }

    public boolean isEmpty() {
        return this.list.isEmpty();
    }

    public boolean contains(Object element) {
        return this.list.contains(element);
    }

    public Iterator<T> iterator() {
        return this.list.iterator();
    }

    public Object[] toArray() {
        return this.list.toArray();
    }

    public <E> E[] toArray(E[] elements) {
        return this.list.toArray(elements);
    }

    public boolean add(T element) {
        this.list.add(findIndex(element), element);
        return true;
    }

    public T getFirst() {
        return this.list.getFirst();
    }

    public T getLast() {
        return this.list.getLast();
    }

    public int size() {
        return this.list.size();
    }

    public LinkedQueue<T> append(T element) {
        this.list.add(findIndex(element), element);
        return this;
    }

    public boolean remove(Object element) {
        return this.list.remove(element);
    }

    public boolean containsAll(Collection<?> elements) {
        return this.list.containsAll(elements);
    }

    public boolean addAll(Collection<? extends T> elements) {
        if (CollectionUtils.isEmpty(elements))
            return false;
        elements.forEach(this::append);
        return true;
    }

    public boolean removeAll(Collection<?> elements) {
        return this.list.removeAll(elements);
    }

    public boolean retainAll(Collection<?> elements) {
        return this.list.retainAll(elements);
    }

    public void clear() {
        this.list.clear();
    }

    private int findIndex(T element) {
        if (isEmpty())
            return 0;
        if (this.list.size() == 1)
            return (this.comparator.compare(this.list.get(0), element) > 0) ? 0 : 1;
        return dichotomyFindIndex(element, 0, this.list.size() - 1);
    }

    private int dichotomyFindIndex(T element, int start, int end) {
        if (this.comparator.compare(this.list.get(start), element) > 0)
            return start;
        if (this.comparator.compare(this.list.get(end), element) < 0)
            return end + 1;
        if (end - start <= 1)
            return end;
        int middle = (start + end) / 2;
        if (this.comparator.compare(this.list.get(middle), element) < 0)
            return dichotomyFindIndex(element, middle, end);
        return dichotomyFindIndex(element, start, middle);
    }

    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (!(o instanceof LinkedQueue))
            return false;
        LinkedQueue<?> that = (LinkedQueue) o;
        if ((this.list != null) ? !this.list.equals(that.list) : (that.list != null))
            return false;
        return (this.comparator != null) ? this.comparator.equals(that.comparator) : ((that.comparator == null));
    }

    public int hashCode() {
        int result = (this.list != null) ? this.list.hashCode() : 0;
        result = 31 * result + ((this.comparator != null) ? this.comparator.hashCode() : 0);
        return result;
    }

    public String toString() {
        return this.list.toString();
    }
}
